package p2;

// Murat Muratovic
// CS 4500 03/23/2012
// P2

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class P2 {

	public static P2Graph graph = new P2Graph();
	public static P2SecondGraph graph2 = new P2SecondGraph();
	public static Boolean firstTime = true;
	public static double adjMatrix[][];
        private static long startTime = 0;
        private static long currentTime = 0;
        private final static boolean DEBUG_OUTPUT = true;

	public static void main(String[] args) {
                startTime = System.currentTimeMillis();
		graph.setDirected();
		List<String> mapFile = new ArrayList<String>();
		List<String> routeFile = new ArrayList<String>();
		String mapFileName = "";
		String routeFileName = "";
                startTimer();
		try {
			if (args.length == 0) {
//				printError("Usage: > run datafile [problemfile]", true);
//				System.exit(1);
                                File dir1 = new File(".");
                                System.out.println(dir1.getCanonicalPath());
                                mapFileName = "datafile";
				routeFileName = "problemfile";
				mapFile = readFile(mapFileName);
				routeFile = readFile(routeFileName);
			} else if (args.length == 1) {
				mapFileName = args[0];
				mapFile = readFile(mapFileName);
				System.out.println("Enter the route you want to calculate, "
						+ "terminate by empty line: ");
				processRouterFromInput(mapFile);
			} else if (args.length == 2) {
				mapFileName = args[0];
				routeFileName = args[1];
				mapFile = readFile(mapFileName);
				routeFile = readFile(routeFileName);
			} else {
				printError("Usage:\n> run datafile [problemfile]\n", true);
			}
		} catch (Exception ex) {
			ex.printStackTrace();
			System.exit(1);
		}
		try {
			for (int ln = 0; ln < routeFile.size(); ln++) {
				processLine(mapFile, routeFile.get(ln), ln);
			}
		} catch (Exception e) {
			printError(e.getMessage(), true);
		}
                
                if (DEBUG_OUTPUT)
                    printElapsedTime("Overall time");
                
		System.out.println();
		System.exit(1);
	}

	public static void processRouterFromInput(List<String> mapFile) {
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		int ln = 0;
		try {
			System.out.print("\nPath:");
			String line = br.readLine();
			while (true) {
				// until no other inputs to proceed
				if (line.compareToIgnoreCase("") == 0)
					break;
				processLine(mapFile, line, ln);
				System.out.print("\nPath:");
				line = br.readLine();
			}
		} catch (Exception e) {
			printError(e.getMessage(), true);
		}
		System.out.println();
		System.exit(1);
	}

	public static void processLine(List<String> mapFile, String routeLine,
			int ln) {
		// = buildMapFromFile(mapFile);
		Map<String, Vertex> citiesMap;
		Vertex[] verticesMap;
		int type;
		Vertex from;
		Vertex to;
		try {
			String[] route = routeLine.split(" ");
			if (route.length < 2)
				printError("Wrong # of arguments on line:" + (ln + 1), true);
			type = Integer.parseInt(route[0]);
			citiesMap = buildMapFromFile(mapFile);
			verticesMap = buildVertex(citiesMap);
			from = citiesMap.get(route[1]);
			System.out.println("\n" + routeLine);
			if (from == null)
				printError(route[1] + " Not found in datafile, line:"
						+ (ln + 1), true);
			if (type == 1) {
				if (route.length != 3)
					printError("Wrong number of arguments on line:" + (ln + 1),
							true);
				to = citiesMap.get(route[2]);
				if (to == null)
					printError(route[2] + " Not found in datafile, line:"
							+ (ln + 1), true);
				System.out.print("   ");
				printRoute(from, to);
			} else if (type == 2 && route.length > 2) {
				printRouteForOptionTwo(route, citiesMap, ln);
			} else if (type == 3) {
                                long typeThreeStartTime = System.currentTimeMillis();
				if (route.length != 2)
					printError("Wrong number of arguments on line:" + (ln + 1),
							true);
				String newRoute = "3 " + from;
				for (Vertex v : verticesMap) {
					if (from == v)
						continue;
					// printRoute(from, v);
					newRoute = newRoute + " " + v;
				}
				printRouteForOptionTwo(newRoute.split(" "), citiesMap, ln);
			} else {
				printError("Invalid Option on Line:" + ln + 1, true);
			}
		} catch (Exception e) {
			printError(e.getMessage(), true);
		}
	}

	private static void printRouteForOptionTwo(String[] route,
			Map<String, Vertex> citiesMap, int ln) {

		Vertex from = citiesMap.get(route[1]);
		Vertex to;
		double prevDistance = -1.0;
		double distance;
		String thisRoute = "";
		ArrayList<String> shortestRoute = new ArrayList<String>();
		for (int t = 2; t < route.length; t++) {
			to = citiesMap.get(route[t]);
			if (to == null)
				printError(route[t] + " Not found in map,Line:" + (ln + 1),
						true);
			if (from == to)
				continue;
			Routes allPs = new Routes(graph2, from.toString(), to.toString());
			ArrayList<List<String>> allPossiblePaths = allPs.show();
			allPossiblePaths = new ArrayList<List<String> >(new HashSet
					(allPossiblePaths));
			for (int p = 0; p < allPossiblePaths.size(); p++) {
				if (allPossiblePaths.get(p).size() >= route.length - 1) {
					List<String> onePath = allPossiblePaths.get(p);
					int found = 0;
					for (int s = 1; s < route.length; s++) {
						if (onePath.contains(route[s])) {
							found += 1;
						}
					}
					if (found < (route.length - 1)) {
					} else {
						// System.out.println(onePath);
						distance = 0.0;
						thisRoute = "";
						for (int r = 1; r < onePath.size(); r++) {
							P2Nodes frmPath = new P2Nodes<String>(
									onePath.get(r - 1));
							P2Nodes toPath = new P2Nodes<String>(onePath.get(r));
							distance += adjMatrix[graph.indexOf(frmPath)][graph
									.indexOf(toPath)];
							if (thisRoute.equals("")) {
								thisRoute = frmPath
										+ " "
										+ adjMatrix[graph.indexOf(frmPath)][graph
												.indexOf(toPath)] + " "
										+ toPath;
							} else {
								thisRoute = thisRoute
										+ " "
										+ adjMatrix[graph.indexOf(frmPath)][graph
												.indexOf(toPath)] + " "
										+ toPath;
							}
						}
						if (prevDistance < 1 || distance < prevDistance) {
							prevDistance = distance;
							shortestRoute = new ArrayList<String>();
							shortestRoute.add(distance + " " + thisRoute);
						} else if (distance == prevDistance) {
							shortestRoute.add(distance + " " + thisRoute);
						}
					}
				}
			}
		}
		if (shortestRoute.size() < 1) {
			System.out.println("   Path not found!");
		} else if (shortestRoute.size() == 1) {
			System.out.println("   " + shortestRoute.get(0));
		} else {
			System.out.println("   " + shortestRoute.size()
					+ " different paths:");
			for (int f = 0; f < shortestRoute.size(); f++) {
				System.out.println("     " + shortestRoute.get(f));
			}
		}
	}

	public static List<String> readFile(String fn) {
		List<String> lines = new ArrayList<String>();
		try {
			FileInputStream fs = new FileInputStream(fn);
			DataInputStream in = new DataInputStream(fs);
			BufferedReader br = new BufferedReader(new InputStreamReader(in));
			String strLine = null;
			String line = null;
			while ((line = br.readLine()) != null) {
				if (line != "" && line != null)
					lines.add(line);
			}
			br.close();
		} catch (Exception e) {
			printError(e.getMessage(), true);
		}
		return lines;
	}

	public static void printError(String msg, boolean exit) {
		System.out.println("Error: " + msg);
		if (exit)
			System.exit(-1);

	}

	public static Vertex[] buildVertex(Map<String, Vertex> mCities) {
		Vertex[] vertices = mCities.values().toArray(
				new Vertex[mCities.values().size()]);
		return vertices;
	}

	public static Map<String, Vertex> buildMapFromFile(List<String> file) {
		
		Map<String, Vertex> mCities = new HashMap<String, Vertex>(); 
		// Variables to hold graph from datafile
		
		Map<String, ArrayList<TempEdge>> mEdges = new HashMap<String, ArrayList<TempEdge>>(); 
		// Variables to hold graph of edges for each node
		try {
			// Verify the number entered on the first line is 
			// the same as the number of the strings 
			// on second line
			int nCities = Integer.parseInt(file.get(0));
			String cities[] = file.get(1).split(" ");
			if (nCities != cities.length)
				printError(
						"The number in 1st line different from number of the strings in 2nd line",
						true);

			// Generate map from the nodes and declare the TempEdge for each node
			for (int c = 0; c < nCities; c++) {
				// Add each node to the map
				mCities.put(cities[c], new Vertex(cities[c])); 
				// declare the TempEdge for each node
				mEdges.put(cities[c], new ArrayList<TempEdge>()); 
			}
			
			// Generate map for the Edges of each node
			String cLine[];
			for (int i = 2; i < file.size(); i++) {
				// System.out.println(i + "\t" + file.get(i)); // Print each
				// line from the list
				cLine = file.get(i).split(" ");
				if (cLine.length != 3) 
					// number of parameters is not 3 then
					// error and exit
					printError("Wrong number of parameters on line#"
							+ cLine.length, true);
				int distance = Integer.parseInt(cLine[2]); 
				// Distance between the cities as 3rd parameter
				try {
					mEdges.get(cLine[0]).add(
							new TempEdge(mCities.get(cLine[1]), distance)); 
					// Add an edge for first node to second node on distance

					mEdges.get(cLine[1]).add(
							new TempEdge(mCities.get(cLine[0]), distance)); 
					// Add an edge for second city to first city on distance
														

					if (firstTime) {
						graph2.addEdge(cLine[0], cLine[1]); // For BFS for All
															// Possible Routes

						// For Distance
						P2Nodes<String> a = new P2Nodes<String>(cLine[0]);
						P2Nodes<String> b = new P2Nodes<String>(cLine[1]);
						int aPos = graph.indexOf(a);
						int bPos = graph.indexOf(b);
						// If a does not exist in the graph yet.
						if (aPos == -1)
							aPos = graph.addNode(a);

						// If b does not exist in the graph yet.
						if (bPos == -1)
							bPos = graph.addNode(b);

						double weight = Double.parseDouble(cLine[2]);
						Edge edge1 = new Edge(graph.getNodeAt(aPos),
								graph.getNodeAt(bPos), weight);
						Edge edge2 = new Edge(graph.getNodeAt(bPos),
								graph.getNodeAt(aPos), weight);
						graph.addEdge(edge1);
						graph.addEdge(edge2);
					}

				} catch (Exception ex) {
					printError(
							"Invalid string on line: " + i + "\t" + file.get(i),
							true);
				}
			}
			// Link each city with its edges
			for (int c = 0; c < nCities; c++) {
				mCities.get(cities[c]).adjacencies = mEdges.get(cities[c])
						.toArray(new TempEdge[mEdges.get(cities[c]).size()]);

			}
			// Build vertices list from the map of cities
			if (firstTime) {
				firstTime = Boolean.FALSE;
				adjMatrix = graph.getAdjacencyMatrix();
				for (int k = 0; k < adjMatrix.length; k++)
					for (int i = 0; i < adjMatrix.length; i++)
						for (int j = 0; j < adjMatrix.length; j++)
							adjMatrix[i][j] = Math.min(adjMatrix[i][j],
									adjMatrix[i][k] + adjMatrix[k][j]);
			}
			return mCities;
		} catch (Exception e) {
			printError(e.getMessage(), true);
		}
		return null;
	}

	public static void computePaths(Vertex source) {
		source.minDistance = 0.;
		PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
		vertexQueue.add(source);

		while (!vertexQueue.isEmpty()) {
			Vertex u = vertexQueue.poll();

			// Visit each edge exiting u
			for (TempEdge e : u.adjacencies) {
				Vertex v = e.target;
				double weight = e.weight;
				double distanceThroughU = u.minDistance + weight;
				if (distanceThroughU < v.minDistance) {
					vertexQueue.remove(v);
					v.minDistance = distanceThroughU;
					v.previous = u;
					vertexQueue.add(v);
				}
			}
		}
	}

	public static List<Vertex> getShortestPathTo(Vertex target) {
		List<Vertex> path = new ArrayList<Vertex>();
		for (Vertex vertex = target; vertex != null; vertex = vertex.previous) {
			path.add(vertex);
		}
		Collections.reverse(path);
		return path;
	}

	public static void printRoute(Vertex from, Vertex to) {
		if (from == to) {
			// Skip if from and to are same cities
			// Validate if cities entered are the same
			System.out.print("0 " + from + " 0 " + to);
			return;
		}
		computePaths(from);
		List<Vertex> path = getShortestPathTo(to);
		if (path.size() == 1) {
			System.out.println("   Path not found!");
		} else {
			int cPath = 0;
			double tmpDist = 0.0;
			for (Vertex p : path) {
				cPath += 1;
				if (cPath == 1) {
					System.out.print(to.minDistance + " " + p);
				} else if (cPath == path.size() + 1) {
					System.out.print(" " + p);
				} else {
					System.out.print(" " + (p.minDistance - tmpDist) + " " + p);
					tmpDist = p.minDistance;
				}
			}
			System.out.println("");
		}
	}
        
        public static void startTimer()
        {
            startTime = System.currentTimeMillis();
        }
        
        public static void printElapsedTime(String msg)
        {
            currentTime = System.currentTimeMillis();
            System.out.println("[" + msg + "] Elapsed time: " + (currentTime - startTime) + " ms");
        }
        
        /*
         * Class used to make threads to complete the specified problems
         * in the problem file.  
         */
        private class pathingThreadHelper
        {
            public pathingThreadHelper(ArrayList<String> mapFile, ArrayList<String> route)
            {
                
            }
        }
        
        /*
         * This is a thread which processes a problem line
         */
        private class pathingThread extends Thread
        {
            private boolean isComplete = false;
            private ArrayList<String> mapFile;
            private String routeLine;
            private int ln;
            
            public pathingThread(ArrayList<String> mapFile, String routeLine, int ln)
            {
                this.mapFile = (ArrayList<String>) mapFile.clone();
                this.routeLine = routeLine;
                this.ln = ln;
            }
            
            public void run() 
            {
                processLine(mapFile, routeLine, ln);
                isComplete = true;
            }
            
            public boolean isPathingComplete()
            {
                return isComplete;
            }
            
            public void processLine(List<String> mapFile, String routeLine, int ln) 
            {
		// = buildMapFromFile(mapFile);
		Map<String, Vertex> citiesMap;
		Vertex[] verticesMap;
		int type;
		Vertex from;
		Vertex to;
		try {
			String[] route = routeLine.split(" ");
			if (route.length < 2)
				printError("Wrong # of arguments on line:" + (ln + 1), true);
			type = Integer.parseInt(route[0]);
			citiesMap = buildMapFromFile(mapFile);
			verticesMap = buildVertex(citiesMap);
			from = citiesMap.get(route[1]);
			System.out.println("\n" + routeLine);
			if (from == null)
				printError(route[1] + " Not found in datafile, line:"
						+ (ln + 1), true);
			if (type == 1) {
				if (route.length != 3)
					printError("Wrong number of arguments on line:" + (ln + 1),
							true);
				to = citiesMap.get(route[2]);
				if (to == null)
					printError(route[2] + " Not found in datafile, line:"
							+ (ln + 1), true);
				System.out.print("   ");
				printRoute(from, to);
			} else if (type == 2 && route.length > 2) {
				printRouteForOptionTwo(route, citiesMap, ln);
			} else if (type == 3) {
                                long typeThreeStartTime = System.currentTimeMillis();
				if (route.length != 2)
					printError("Wrong number of arguments on line:" + (ln + 1),
							true);
				String newRoute = "3 " + from;
				for (Vertex v : verticesMap) {
					if (from == v)
						continue;
					// printRoute(from, v);
					newRoute = newRoute + " " + v;
				}
				printRouteForOptionTwo(newRoute.split(" "), citiesMap, ln);
			} else {
				printError("Invalid Option on Line:" + ln + 1, true);
			}
		} catch (Exception e) {
			printError(e.getMessage(), true);
		}
            }
        }
}
